<?php
/** 
 * 
 *
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id: PriorityQueue.php 14 2006-11-28 22:05:19Z rdff3 $
 */
/**
 *
 */
require_once( "util/AbstractQueue.php" );

/** 
 * Class PriorityQueue
 *
 * An unbounded priority queue based on a priority heap. This queue orders elements according to an order specified at construction time, 
 * which is specified either according to their natural order (see Comparable), or according to a Comparator, depending on which constructor
 * is used. A priority queue does not permit null elements. A priority queue relying on natural ordering also does not permit insertion of 
 * non-comparable objects (doing so may result in ClassCastException).
 * 
 * The head of this queue is the least element with respect to the specified ordering. If multiple elements are tied for least value, the head 
 * is one of those elements -- ties are broken arbitrarily. The queue retrieval operations poll, remove, peek, and element access the element 
 * at the head of the queue.
 *  
 * This class and its iterator implement all of the optional methods of the Collection and Iterator interfaces except for the remove method. The  
 * Iterator provided in method iterator() is not guaranteed to traverse the elements of the PriorityQueue in any particular order. If you need  
 * ordered traversal, consider using Arrays.sort(pq.toArray()).
 * 
 * Implementation note: this implementation provides O(log(n)) time for the insertion methods (offer, poll, removeHead and add) methods; linear 
 * time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size).
 *
 * This class is a member of the PHP Collections Framework. 
 *
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id: PriorityQueue.php 14 2006-11-28 22:05:19Z rdff3 $
 */
class PriorityQueue extends AbstractQueue {

	// ================================== Private Members ===============================================================

	/**
	 * The comparator used by this priority queue.
	 */ 
	private $comparator;

	/**
	 * Internal storage of the heap size.
	 */
	private $size;
	
	/**
	 * Internal storage of the actual heap array. 
	 */
	private $heap;
	
	// ================================== Public Functions =================================================================
	
	/**
	 * Creates a PriorityQueue that orders its elements according to the specified comparator.  
	 *
	 * Creates a PriorityQueue that orders its elements according to the specified comparator. It adds all the elements of the Collection $col 
	 * to this PriorityQueue.  Adding the elements of Collection $col is done in O(n) time with a buildHeap algorithm.
	 *
	 * @param Comparator $c the comparator used to order this priority queue.  If null, then the order depends on the elements' natural ordering.
	 * @param Collection $col the collection whose elements are to be placed into this priority queue.
	 * @throws ClassCastException - if elements of the specified collection cannot be compared to one another according to the priority queue's ordering. 
	 * @throws NullPointerException - if c or any element within it is null
	 */
	public function __construct( Comparator $c = null, Collection $col = null ) {
		$this->comparator = $c;
		$this->clear();
		if (!is_null($col))
			$this->buildHeap( $col->toArray() );
			
	}
	
	/**
	 * Adds the specified element to this queue.
	 *
	 * @param Object $o the element
	 * @returns boolean true (as per the general contract of Collection->add)
	 * @throws ClassCastException - if the specified element cannot be compared with elements currently in the priority queue according to 
	 * 		the priority queue's ordering. 
	 * @throws NullPointerException - if the specified element is null.
	 */
	public function add( Object $o ) {
		if (is_null($o))
			throw new NullPointerException();
	
		$hole = ++$this->size;
		$this->heap[$hole] = $o;
		
		$this->percolateUp($hole);
		return true;
	}
	
	/**
	 * Removes all elements from the priority queue.
	 *
	 * The queue will be empty after this call returns.
	 */
	public function clear() {
		$this->size = 0;
		$this->heap = array();
	}
	
	/**
	 * Returns the comparator used to order this collection, or null  if this collection is sorted according to its elements natural ordering (using Comparable).
	 *
	 * @return Comparator the comparator used to order this collection, or null if this collection is sorted according to its elements natural ordering.
	 */
	public function comparator() {
		return $this->comparator;
	}
	
	
	/**
	 * Returns the number of elements in this collection.
	 *
	 * @returns int the nubmer of elements in this collection.
	 */
	public function size() {
		return $this->size;
	}
	
	/**
	 * Returns an iterator over the elements in this queue.
	 *
	 * The iterator does not return the elements in any particular order.  This implementation also does not support the iterator->remove() method.
	 *
	 * @return CollectionIterator an iterator over the elements in this queue.
	 */
	public function iterator() {
		return new PriorityQueue_Iterator( $this );
	}
	
	/** 
	 * Inserts the specified element into this priority queue.
	 *
	 * @param Object $o the element to insert
	 * @returns boolean true
	 * @throws ClassCastException - if the specified element cannot be compared with elements currently in the priority queue according to 
	 * 		the priority queue's ordering. 
	 * @throws NullPointerException - if the specified element is null.
	 */
	public function offer( Object $o ) {
		return $this->add( $o );
	}
	
	/**
	 * Retrieves, but does not remove, the head of this queue, returning null if this queue is empty.
	 *
	 * @return Object the head of this queue, or null if this queue is empty.
	 */
	public function peek() {
		return $this->findMin();
	}
	
	/**
	 * Retrieves and removes the head of this queue, or null  if this queue is empty.
	 *
	 * @return Object the head of this queue, or null if this queue is empty.
	 */
	public function poll() {
		return $this->deleteMin();
	}
	
	
	/**
	 * Removes a single instance of the specfified element from this queue, if it is present.
	 *
	 * @param Object $o element to be removed from this collection, if present.
	 * @returns boolean true if the collection contained the specified element.
	 */
	public function remove( Object $o ) { 
		$return_value = false;
		for ($i = 1; $i <= $this->size; $i++) {
		
			if ($this->heap[$i]->equals( $o ) ) {
				$this->heap[$i] = $this->heap[ $this->size ];
		
				unset($this->heap[$this->size--]);
				$this->siftDown( $i );
				$return_value = true;
				break;
			}
			
		}
		return $return_value;
	}
	
	
	public function isHeap() {
		$k = 1;
		
		for ($i = 1; $i <= (int) ($this->size / 2); $i++) {
			if ((2 * $i) <= $this->size and $this->cmp( $this->heap[$i], $this->heap[2 * $i] ) > 0)
				return false;
			if ((2 * $i) < $this->size and $this->cmp( $this->heap[$i], $this->heap[2 * $i + 1] ) > 0)
				return false;
		}
		return true;
	}
	
	public function getHeap() {
		return $this->heap;
	}
	
	
	// ============================================== Private Funcitons =========================================================
	
	/**
	 * Moves a heap element up from the last element in the heap array to its correct position.
	 *
	 * @param int $hole - the hole (location) to be percolated up to its correct position.
	 */
	private function percolateUp( $hole ) { // use for adds
		$k = $hole;
		do  {
			$j = $k;
			
			if ($j > 1 and $this->cmp( $this->heap[(int) ($j / 2)], $this->heap[$k] ) >= 0)
				$k = (int) ($j / 2);
				
			$tmp = $this->heap[$k];
			$this->heap[$k] = $this->heap[$j];
			$this->heap[$j] = $tmp;
			
		} while( $j != $k );
	}
	
	/**
	 * Moves a heap element down from it's current position to its correct position in the array.
	 *
	 * @param int $hole - the hole (location) to be sifted down to its correct position.
	 */
	private function siftDown( $hole ) { // use for removes
		$k = $hole;
		do {
			$j = $k;			
			
			if ((2 * $j) <= $this->size and $this->cmp( $this->heap[$k], $this->heap[2*$j] ) > 0) 
				$k = 2 * $j;
			if ((2 * $j) < $this->size and $this->cmp( $this->heap[$k], $this->heap[2*$j + 1] ) > 0) 
				$k = 2 * $j + 1;
								
			$tmp = $this->heap[$k];
			$this->heap[$k] = $this->heap[$j];
			$this->heap[$j] = $tmp;
			
		} while ($j != $k);
		
		
	}
	
	/**
	 * Internal compare function.
	 *
	 * This function will compare two objects in the heap.  If a comparator has be specified, the comparator will be used to compare to object, else the
	 * elements natural ordering will be used.  
	 *
	 * @param Object $o1 the first object to compare.
	 * @param Object $o2 the second object to compare.
	 * @returns int a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater 
	 * 		than the second.
	 * 
	 * @throws ClassCastException - if the elements are not mutually comparable.
	 */
	private function cmp( Object $o1, Object $o2 ) { // internal comparison function, abstracts out the comparator or natural ordering
		if (is_null($this->comparator))
			return $o1->compareTo($o2);
		else
			return $this->comparator->compare( $o1, $o2 );
	}
	
	/**
	 * Returns, but does not remove, the minimum element in this priority queue.
	 *
	 * @returns Object the minimum element in this priority queue.
	 * @throws UnderflowException - if this priority queue is empty.
	 */
	private function findMin() {
		if ($this->isEmpty() )
			throw new UnderflowException( "Empty heap");
		return $this->heap[1];
	}
	
	
	/**
	 * Removes the minimum element in this priority queue.
	 *
	 * @returns Object the minimum element in this priority queue.
	 * @throws UnderflowException - if this priority queue is empty.
	 */
	private function deleteMin() {
		$minItem = $this->findMin();
		$this->heap[1] = $this->heap[ $this->size ];
		
		unset($this->heap[$this->size--]);
		
		if ($this->size > 1)
			$this->siftDown(1);
			
		return $minItem;
	}
	
	/**
	 * Builds a heap in O(n) time.
	 *
	 * @param array $new_array the array to build the heap out of.
	 */
	private function buildHeap( $new_array ) { 
		$this->size = sizeof($new_array);
		$this->heap = $new_array;
		
		for ($i = $this->size / 2; $i > 0; $i-- ) {
			if (!is_null($this->heap[$i]))
				$this->siftDown($i);
		}
	}
}
/**
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id: PriorityQueue.php 14 2006-11-28 22:05:19Z rdff3 $
 * @internal
 */
class PriorityQueue_Iterator implements CollectionIterator {
	protected $pq;
	
	protected $java_current = 0;
	protected $php_current = 1;
	
	public function __construct( PriorityQueue $queue ) {
		$this->pq = $queue;
	}
	
	// Java Style Iteration
	public function hasNext() { 
		return $this->java_current != $this->pq->size();
	}
	public function getNext() {
		if ($this->hasNext()) {
			$heap = $this->pq->getHeap();
			return $heap[ ++$this->java_current ];
		}
		else
			throw new NoSuchElementException();
	}
	public function remove() {
		throw new UnsupportedOperationException( );
	}
	
	// PHP Style Iteration with foreach
	public function current() { 
		$heap = $this->pq->getHeap();
		return $heap[ $this->php_current ];
	}
	public function key() {
		throw new UnsupportedOperationException( );
	}
	public function valid() {
		return $this->php_current <= $this->pq->size();
	}
	public function next() { 
		$this->php_current++;
	}
	public function rewind() { 
		$this->php_current = 1;
	}
	
}

?>